<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <title>线性探测散列表</title>
</head>

<body>
  <h1>Todo?线性探测散列表</h1>
  <p>如果数组的大小是待存储数据个数的1.5倍，使用开链法；如果数组大小是待存储数据的两倍及两倍以
    上，那么使用线性探测法。
  </p>
  <script>
    function HashTable() {
      this.table = new Array(137); //用来保存键
      this.values = []; //用来保存值
      this.simpleHash = simpleHash;
      this.betterHash = betterHash;
      this.showDistro = showDistro;
      this.put = put;
      this.get = get;
    }
    // 防碰撞，线性探测的put方法
    function put(key, data) {
      //var pos = this.betterHash(key);
      var pos = this.simpleHash(key); //会产生碰撞
      console.log(key + "的散列值=" + pos);
      if (this.table[pos] == undefined) {
        this.table[pos] = key;
        this.values[pos] = data;
      } else {
        while (this.table[pos] != undefined) {
          pos++;
        }
        this.table[pos] = key;
        this.values[pos] = data;
      }
    }
    // 简单的散列函数
    function simpleHash(string) {
      var total = 0;
      for (var i = 0; i < string.length; ++i) {
        total += string.charCodeAt(i);
      }
      return total % this.table.length;
    }
    //更好的散列函数
    function betterHash(string) {
      var H = 37;
      var total = 0;
      for (var i = 0; i < string.length; ++i) {
        total += H * total + string.charCodeAt(i);
      }
      total = total % this.table.length;
      if (total < 0) {
        total += this.table.length - 1;
      }
      return parseInt(total);
    }
    //显示散列表中的数据
    function showDistro() {
      var n = 0;
      for (var i = 0; i < this.table.length; ++i) {
        if (this.table[i] != undefined) {
          console.log(this.table[i] + ": " + this.values[i]);
        }
      }
    }
    //产生一个min到max的随机数
    function getRandomInt(min, max) {
      return Math.floor(Math.random() * (max - min + 1)) + min;
    }
    //产生测试数据，一个九位的ID+二位的成绩，字符串
    function genStuData(arr) {
      for (var i = 0; i < arr.length; ++i) {
        var num = "";
        for (var j = 1; j <= 9; ++j) {
          num += Math.floor(Math.random() * 10);
        }
        num += getRandomInt(50, 100);
        arr[i] = num;
      }
    }
    // 防碰撞，线性探测的get方法
    function get(key) {
      var hash = -1;
      // hash = this.betterHash(key);
      hash = this.simpleHash(key);
      if (hash > -1) {
        for (var i = hash; this.table[i] != undefined; i++) {
          if (this.table[i] == key) {
            return this.values[i];
          }
        }
      }
      return undefined;
    }
    //测试
    var hTable = new HashTable();
    var someNames = [
      ["David", 70],
      ["Jennifer", 90],
      ["Donnie", 50],
      ["Raymond", 66],
      ["Cynthia", 87],
      ["Mike", 34],
      ["Clayton", 90],
      ["Danny", 73],
      ["Jonathan", 74]
    ];
    for (var i = 0; i < someNames.length; ++i) {
      hTable.put(someNames[i][0], someNames[i][1]);
    }
    console.log("-----------------");
    hTable.showDistro();
    console.log("-----------------");
    console.log("Clayton:" + hTable.get("Clayton"));
    console.log("Raymond:" + hTable.get("Raymond"));
  </script>
</body>

</html>
